package LearnAlgorithm.d_标准查找算法and标准排序算法;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;

/**
 * 数据中存在负数也能安全排序
 * 运用了偏移量
 * 除法是向下取整
 */
public class b9a桶排序 {
	public static void main(String[] args) {
		int[] arr = new int[] {9,8,6,5,4,7,1,10,15,14,16,-6};
		long before = System.currentTimeMillis();
		bucketSort2(arr);
		util.Util.duration(before);
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
	}

	/**
	 * 桶排序
	 * 最好O(N)
	 * 最坏O(NlogN)
	 * @param arr
	 */
	public static void bucketSort2(int[] arr) {
		int min = minFind(arr);//定义最小值
		int current = 0;//定义回填时的待存入数值的元素的指针
		//初始化桶
		int bucketNum = (maxFind(arr) - min) / arr.length + 1;//定义桶数量；有偏移量；固定公式；已经很想办法节省空间了；需要保证至少有一个桶，故而需要加个1
		//如果每个桶的坑数是利用数组实现的话，坑数需满足：
		//cnt = (mx - mn) / bucketNum + 1，需要保证每个桶至少要能装1个数，故而需要加个1
		//求得了bucketNum和cnt后，即可知第一个桶装的数据范围为 [mn, mn + bucketNum)，第二个桶为 [mn + bucketNum, mn + 2 * bucketNum)，…，以此类推
		ArrayList<LinkedList<Integer>> bucketArrayList = new ArrayList<LinkedList<Integer>>(bucketNum);//创建坑们
		for (int i = 0; i < bucketNum; i++) {//给每个坑放上桶
			bucketArrayList.add(new LinkedList<Integer>());//桶是集合
		}
		//遍历原数组，逐个存放到桶们中
		for (int i = 0; i < arr.length; i++) {
			bucketArrayList.get((arr[i] - min) / (arr.length)).add(arr[i]);//存在偏移量，注意
		}
		//对每个桶中存入的元素进行排序
		//其实桶排序的入桶规则可以自定义；利用自己写的链表结构就能自定义入桶规则
		for (int i = 0; i < bucketArrayList.size(); i++) {
			if (!bucketArrayList.get(i).isEmpty()) {//如果有空桶，就不排序
				java.util.Collections.sort(bucketArrayList.get(i));//TODO 这个排序算法是...
			}
		}
		//将每个桶中的元素回填进数组
		for (int i = 0; i < bucketNum; i++) {//看着是双层循环，其实仍然O(N)
			LinkedList<Integer> bucket = bucketArrayList.get(i);
			if (bucket.isEmpty()) {
				continue;
			}
			Iterator<Integer> iterator = bucket.iterator();
			while (iterator.hasNext()) {
				arr[current++] = iterator.next();
			}
		}
	}

	/**
	 * 桶排序
	 * 最好O(N)
	 * 最坏O(NlogN)
	 * @param arr
	 */
	public static void bucketSort(int[] arr) {
		int min = minFind(arr);//定义最小值
		int current = 0;//定义回填时的待存入数值的元素的指针
		//初始化桶
		int bucketNum = (maxFind(arr) - min) / arr.length + 1;//定义桶数量；有偏移量；固定公式；已经很想办法节省空间了
		ArrayList<ArrayList<Integer>> bucketArrayList = new ArrayList<ArrayList<Integer>>(bucketNum);//创建坑们
		for (int i = 0; i < bucketNum; i++) {//给每个坑放上桶
			bucketArrayList.add(new ArrayList<Integer>());//桶是集合
		}
		//遍历原数组，逐个存放到桶们中
		for (int i = 0; i < arr.length; i++) {
			bucketArrayList.get((arr[i] - min) / (arr.length)).add(arr[i]);//存在偏移量，注意
		}
		//对每个桶中存入的元素进行排序
		for (int i = 0; i < bucketArrayList.size(); i++) {
			if (!bucketArrayList.get(i).isEmpty()) {//如果有空桶，就不排序
				java.util.Collections.sort(bucketArrayList.get(i));//TODO 这个排序算法是...
			}
		}
		//将每个桶中的元素回填进数组
		for (int i = 0; i < bucketArrayList.size(); i++) {
			for (int j = 0; j < bucketArrayList.get(i).size(); j++) {//看着是双层循环，其实仍然O(N)
				arr[current++] = bucketArrayList.get(i).get(j);
			}
		}
	}
	
	public static int minFind(int[] arr) {
		int min = arr[0];
		for (int i = 0; i < arr.length; i++) {
			if (arr[i] < min) {
				min = arr[i];
			}
		}
		return min;
	}
	
	public static int maxFind(int[] arr) {
		int max = arr[0];
		for (int i = 0; i < arr.length; i++) {
			if (max < arr[i]) {
				max = arr[i];
			}
		}
		return max;
	}
}
